package cn.jdemo.algorithm.dynamicProgramming;

/**
 * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 *
 * 动规5步
 * 1.定义
 *      dp[i] 数组下标为i的最长递增子序列的长度
 * 2.递推公式
 *      dp[i]根据dp[j] （j < i）推导出来-->位置i的最长递增子序列的长度 = j从0到i-1各个位置的最长升序子序列 + 1 的最大值
 *      if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
 * 3.初始化
 *      dp[0] = 1
 *      dp[i]其最小递增子序列是1
 * 4.遍历顺序
 * 5.样例:[0,1,0,3,2,3]
 *          dp[i]
 *      0     1
 *      1     2
 *      2     2
 *      3     3
 *      ...   ...
 */
public class LengthOfLIS {
    public static void main(String[] args) {
        int[] nums = {0,1,0,3,2,3};
        int res = new LengthOfLIS().lengthOfLIS(nums);
        System.out.println(res);
    }
    public int lengthOfLIS(int[] nums) {
        int length = nums.length;
        if (length == 1){
            return 1;
        }
        int res = 0;
        int[] dp = new int[length];
        for (int i = 0; i < length; i++) {
            // 初始化
            dp[i] = 1;
        }
        for (int i = 1; i < length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j] ){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }

        // 打印dp[i]
        for (int i = 0; i < dp.length; i++) {
            System.out.println(i+": "+dp[i]);
        }
        return res;
    }
}
